The present invention is directed generally to the field of data processing systems and more particularly to memory systems for use in data processing systems.
Essentially all data processing systems used in artificial intelligence systems require that information be stored and selectively retrieved. The information is normally organized as a database, stored in a memory, which consists of a number of records which are to be retrieved one at a time. Normally, each record is retrieved as a unit. The simplest example of a database retrieval involves retrieving all records that contain one or more keywords. For example, the database might consist of all the articles in a particular set of scientific journals, one article per record. Here one would like to retrieve all articles containing one or more keywords, such as all records containing the words "computing" and "artificial intelligence".
In "expert systems" the database is codified into rules which must be searched repeatedly for rules conforming to a given specification or "query sequence". This type of search, referred to as a "rule-based" search, differs significantly from the search for records containing one or more keywords described above. In a rule-based search the system must choose which of the many rules in the database to apply next to the problem at hand. This choice will depend on the data and relationships between the variables in the problem being solved. The expert system system must select those rules which contain the same data and/or relationships between the variables. A keyword search requires only that the system select rules which contain the same data. For example, these rules may be of the form:
If &lt;condition&gt; then &lt;action or conclusion&gt;. PA1 if (x eats) then (x is hungry).
One of the rules in the data base might be as follows:
If the problem contains the information "Peter eats", the system would be faced with the task of searching all the rules for one containing (x eats). Here x is a variable element which may be replaced by any element in the known information. The above rule together with any others involving "eats" would be retrieved. Once the system has retrieved the rule, it substitutes Peter for x and then concludes that Peter is hungry.
The rule-based search differs significantly from the simple keyword or key element search wherein all records containing one or more keywords are retrieved. In a rule-based system, both the number and order of the elements in the database records are important. Consider a database containing the three records (a,x,b), (a,z,b), and (b,(d,e),a). A request for all records containing "a" and "b" would retrieve all of the above records. However, a request for all "rules" of the form (a,b) would not be satisfied by any of the records, since each record contains 3 elements and the requested rule contains only two. A request for all rules of the form (a,?,b), where ? denotes a variable element which may be satisfied by any constant, a sub-expression, or another variable, would retrieve the first two records, but not the third, since "a" and "b" appear in the wrong order in the third record. Hence even with the concept of a variable, a rule-based retrieval system cannot conveniently be used to select records based on the key elements in an unspecified order.
Similarly, a keyword retrieval system is not well suited to the rule-based retrieval problem since it would retrieve many records in which the elements appear in the wrong order or are present with undesired additional elements. These extra records would have to be discarded by the system after they have been retrieved, which requires both processing time and additional memory for storing the undesired rules.
One problem encountered in implementing artificial intelligence systems using presently available computer hardware is the time required to search a large database for records matching a particular query sequence. To be useful, such a system must contain a very large number of records. Since the time needed to search the database is proportional to the length of the database, as a system having a fixed searching speed becomes "smarter" through the addition of new information in the form of new rules, it also become slower. This problem can only be solved by increasing the searching speed of the system as the size of the database to be searched is increased.
In spite of the numerous improvements which have been made in integrated circuit technology, modern computers differ very little from the original Von Neumann designs. The classical Von Neumann machine consists of a central processing unit and a separate memory organized into words of fixed length. The processing unit fetches data from the memory, one word at a time by specifying the location of the desired word, i.e., its address, relative to the beginning of the memory. To perform the above search, a Von Neumann type central processing unit would sequentially retrieve each word of the database from the memory and would then compare it to each of the keywords in the query sequence which are also stored in the memory.
Since there is a limit to the speed at which a single processing unit can run, Von Neumann type machines in practice are limited as to the size of the database that may be accessed. Even at speeds of 10 million compares per second, a Von Neumann machine would be hard pressed to search the contents of a library which contained, for example, only the law reporter series for the various jurisdictions in the United States.
In addition to its speed limitations, the Von Neumann type architecture also presents a number of limitations because of its inherent hardware dependence. In order to specify a memory address, a fixed number of address lines are used. A system with N address lines can address a memory of 2.sup.N words and no more. To increase the memory capacity beyond this limit, one must increase the number of address lines. This involves both hardware and software alterations, since most systems specify a maximum memory size that the computer's instruction set is capable of addressing. Furthermore, if a portion of the memory is rendered inoperative by a malfunction of one of its components, it is difficult to transfer this storage to an undamaged segment of memory without reprogramming. As the size of the memory is increased in response to the need to store increased numbers of data records, the probability of such a malfunction in one component of the memory increases.
Finally, a large database search problem will require the use of only a small fraction of the instructions present in the central processing unit. A typical central processing unit has literally hundreds of instructions that it is capable of executing varying from input/output instruction for dealing with the outside world to mathematics instructions for combining memory words which represent numbers. The database search problem requires at most 10 to 20 of these instructions. Hence the database search problem under-utilizes the instruction repertoire of the typical central processing unit.
The speed limitations of the central procession unit may be overcome to some degree by constructing a system having multiple central procession units each having access to the memory. However, this solution has its limitations. The number of central processing units that can share a given memory is ultimately limited by the time it takes each central processing unit to access the memory. If the memory bus must be dedicated to each central processing unit for 1/10th of the time, then no more than 10 central processing units can effectively share the same memory. Thus, replicating the central processing unit is not the best solution to the speed limitations of Von Neumann machines.
Even if one could effectively reduce the search time using replicated central processing units, one is still left with the limitations imposed by the hardware. Sooner or later one will want to expand the database beyond these hardware limitations, which is difficult to do in the Von Neumann type machines.
Ideally, one would like to have a modular memory which could be added to a system whenever increases in the size of the database demand it without the concomitant necessity of increasing the number of address lines. This ability to expand the memory will become increasingly more important in those artificial intelligence systems where one seeks to build a machine which is capable of acquiring and using ever increasing amounts of information.